The domain name system (DNS) is a hierarchical distributed naming system for computers or services connected to a network, such as the Internet, and associates human-readable and easily memorized names with internet protocol (IP) addresses. A client computing device may transmit a request for an IP address of a specified domain name, such as www.example.com, to a top level or root name server, which may reply with an identification of a name server that maintains an address list for the .com domain. The client may transmit a request to that name server, which may reply with an address of a name server that maintains a list for the example.com domain. The process may repeat iteratively until the client receives an address for the requested subdomain.
A malicious attacker can intercept these requests and/or responses, and reply with a fake or fraudulent address. For example, an attacker may intercept a request from a client for the address for www.clientbank.com, and may reply with an IP address of a server hosting a fake login page for the bank. When the client user attempts to log in to their bank account, the attacker may capture account numbers and passwords.
To prevent such attacks, the DNS specification has been enhanced with the DNS Security Extensions (DNSSEC) specifications. DNS responses may be digitally signed with a signature calculated by encrypting the response or a portion of the response with an asymmetric cryptographic algorithm. To decrypt and verify a signature received from a name server, such as the name server for www.clientbank.com, the client may obtain the corresponding public key for the name server from the parent name server, e.g. the name server for clientbank.com. That key may also be signed by the parent name server, and the client may obtain the public key for the parent name server from the grandparent name server, e.g. the name server for the .com domain. Accordingly, a chain of trust may be established from the top level or root domain to the name server for the subdomain, with each name server vouching for the name server beneath it in the hierarchy.
Under the DNS specification, if a client requests an address for a subdomain that does not exist, such as non-existent-server.example.com, the authoritative name server responds with a blank resource record. Since the DNSSEC signature of a record is an encrypted copy of the record, this means that there's nothing to sign, and accordingly the response can't be trusted. To provide a signable response, the DNSSEC specification indicates that the name server should reply with a next secure (NSEC) record, which identifies the existing records prior to and after the requested non-existed record. Accordingly, in response to a query for non-exisent-server.example.com, the name server may respond with a signed NSEC record identifying the preceding mail.example.com and the following www.example.com. The client may verify the signature as discussed above, and because mail and www are subsequent records and a record for non-existent-server would have been between them, identify that the requested non-existent-server doesn't exist by implication.
However, by providing the names of the previous and next server in a domain, a malicious attacker can easily obtain the address of every server on the domain by “walking” the tree of addresses: the attacker first requests the address of here-is-a-fake-server-name.example.com, and may receive the names of the real servers ftp.example.com and mail.example.com. The attacker then requests mail-00000001.example.com, and may receive the names of the real servers mail.example.com and www.example.com. Accordingly, by including a slightly incremented or decremented version of each received name, the attacker may determine the names (and therefore addresses, via additional DNS requests) of each real server in the domain, which may then be targeted by other attacks.
To counter this tree-walking, a name server may generate fake server names for an NSEC record identifying non-existent neighbors of a requested server. For example, in response to a request for fake-server-name-b.example.com, the name server may reply with a signed NSEC record identifying names of a fictitious “prior” server fake-server-name-a and fictitious “subsequent” server fake-server-name-c. A client may verify the signature and trust the response, and no additional information is revealed.
However, dynamically generating fictitious neighbor names and digitally signing records may be processor intensive, while creating DNS requests for invalid server names is very easy. Accordingly, a malicious attacker may easily execute a denial of service (DoS) attack against the name server by issuing many requests for addresses of non-existent servers, tying up the name server and preventing it from being able to quickly respond to legitimate client requests. To hide the attacker and prevent filtering, the attacker may use spoofed IP addresses for the requests. This is possible because most DNS queries are transmitted via an unreliable, connectionless, stateless, or asynchronous protocol, such as the user datagram protocol (UDP), which lack a handshaking or synchronization procedure between the sender and receiver.